package com.qst.sort;

import com.qst.queue.MyQueue;

import java.util.Arrays;

/**
 * @author 刘汉平
 * @date 2019/9/10 19:26
 * 基于队列实现的基数排序
 */
public class RadixQueueSort {
    public static void main(String[] args) {
        int[] nusm = {23,14,0,78,34,789,203,404,2,6};
        radixSort(nusm);
        System.out.println(Arrays.toString(nusm));
    }

    /**
     * @param nums
     */
    public static void radixSort(int[] nums){
        //存数组中最大的数字
        int max = Integer.MIN_VALUE;
        for (int i=0;i<nums.length;i++){
            if (nums[i]>max){
                max = nums[i];
            }
        }
        //计算最大的数字是几位数
        int maxLength = (max+"").length();
        //用于临时存储数据的队列,这是一个包含10个队列的数组
        MyQueue[] temp = new MyQueue[10];
        for (int i=0;i<temp.length;i++){
            temp[i] = new MyQueue();
        }
        //根据最大长度的数决定比较的次数
        /*
        * 基数排序，我们找到最大的数字，例如测试数组最大的是789，三位，也就是说我们需要排三轮
        * 第一轮根据各位数排，第二轮根据十位数排，第三轮根据百位数排
        * 但是我们如何通过程序计算个位，十位，百位的数
        * 第一轮的时候我们对一个数字除1然后模10，就可以取到个位了
        * 第二轮的时候我们对一个数字除10然后再摸10，就可以取到十位了
        * 第三轮的时候我们对一个数字除100然后再模10，就可以取到百位了*/
        for (int i=0,n=1;i<maxLength;i++,n*=10){
            //把每一个数字分别计算取余
            for (int j=0;j<nums.length;j++){
                //计算取余
                int ys = nums[j]/n%10;
                //把当前遍历的数据放入指定的队列中
                temp[ys].add(nums[j]);
            }
            //记录取的元素需要放的位置
            int index = 0;
            //把队列中的数字取出来
            for (int k=0;k<temp.length;k++){
                //当队列不为0时
                while (!temp[k].isEmpty()){
                    //取出队列的元素,也就是出队
                    nums[index] =  temp[k].pop();
                    index++;
                }
            }
        }
    }
}
